leetcode/100-n/437. 路径总和 III.md

https://leetcode-cn.com/problems/path-sum-iii/

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) int {
    if root == nil {
        return 0
    }
    return pathSumC(root, targetSum, true)
}

func pathSumC(root *TreeNode, targetSum int, flag bool) int {
    count := 0
    //单独节点
    if root.Left == nil && root.Right == nil {
        if targetSum == root.Val {
            return 1
        }
    }else if targetSum == root.Val {
        count++
    }

    if root.Left != nil {
        //包括当前节点 路径中 向左
        count += pathSumC(root.Left, targetSum - root.Val, false)
        if flag {
            //不包括当前节点
            count += pathSumC(root.Left, targetSum, true)
        }
    }
    if root.Right != nil {
        //包括当前节点 路径中 向右
        count += pathSumC(root.Right, targetSum - root.Val, false)
        if flag {
            //不包括当前节点
            count += pathSumC(root.Right, targetSum, true)
        }
    }
    // fmt.Println(root.Val, targetSum, count)
    return count
}